package 集合.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.LinkedList;
import java.util.Stack;
import java.util.Deque;

public class stack之后缀表达式练习 {
	public static void main(String[] args) {
		String expression = "(100.0+0.25)/2*50/(2+8.78)";
		expression=expression.replace(" ","");//去除表达式中的空格
		List<String> strList = strToList(expression);// 有将String以操作符为界，转成List<String>操作
		List<String> sufferList = getSufferList(strList);
		float cal = cal(sufferList);
		System.out.println("\n" + "计算得到的结果：" + cal);
	}

	static List<String> strToList(String expression) {
		List<String> list = new ArrayList<>();
		String str = "";
		// 按字符（char）遍历表达式
		for (int i = 0; i < expression.length(); i++) {
			char c = expression.charAt(i);
			// 如果是符号，则在符号前后增加空格
			//if (c == '(' || c == ')' || c == '+' || c == '-' || c == '*' || c == '/') {//亦可
			if (String.valueOf(c).matches("['('')''+''-''*''/']")) {//亦可
				str = str + " " + String.valueOf(c) + " ";
			} else { // 如果遇到数字 则原封不动添加
				if (String.valueOf(c).matches("[0123456789'.']")) {
					//System.out.println(c);
					str = str + String.valueOf(c);
					}
				else {
					System.out.println("表达式错误！");
					break;
				}
			}
		}

		String[] strs = str.split(" ");// 用" "分隔str,转成数组
		for (String s : strs) {
			if (!s.equals("")) {
				list.add(s);
			}
		}
		return list;
	}

	// 把中缀表达式转换为后缀表达式
   /*1. 初始化两个栈：运算符栈s1和储存中间结果的栈s2；
   2. 从左至右扫描中缀表达式；
   3. 遇到操作数时，将其压s2；
   4. 遇到运算符时，比较其与s1栈顶运算符的优先级：
       (1)如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
       (2)否则，若优先级比栈顶运算符的高，也将运算符压入s1；
       (3)否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较；
   5. 遇到括号时：
       (1) 如果是左括号“(”，则直接压入s1
       (2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
   6. 重复步骤2至5，直到表达式的最右边
   7. 将s1中剩余的运算符依次弹出并压入s2
   8. 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式*/
	public static List<String> getSufferList(List<String> list) {
		Deque<String> operateStack = new LinkedList<>();// 运算符栈s1
		List<String> tempList = new ArrayList<>();// 中间结果栈s2
		System.out.print("中缀表达式：");
		for (String s : list) {// 显示转换之前的中缀表达式
			System.out.print(s);
		}
		System.out.println();
		for (String item : list) {
			System.out.print("item: " + item);
			System.out.print("    operateStack: ");
			if (!operateStack.isEmpty()) {
				System.out.print(operateStack.toString() + " ");
			}
			System.out.print("    tempList: ");
			for (String str : tempList) {
				System.out.print(str + " ");
			}
			if (item.matches("\\d+(\\.\\d+)?")) { // 遇到操作数时，将其压s2
				tempList.add(item);
			} else if (item.equals("(")) {// 如果是左括号“(”，则直接压入s1
				operateStack.push(item);
			} else if (item.equals(")")) {
				// 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
				while (!operateStack.peek().equals("(")) {// peek取栈顶数据，但不弹出
					tempList.add(operateStack.pop());
				}
				operateStack.pop();// 将"("丢弃
			} else {// 运算符或字符串浏览结束

				while (operateStack.size() != 0 && Operation.getPrior(item) <= Operation.getPrior(operateStack.peek())) {
					// 当前操作符<=oprateStack栈顶操作符，则从oprateStack栈顶弹出操作符压入tempList，直至当前操作符>oprateStack栈顶操作符
					tempList.add(operateStack.pop());
				}
				operateStack.push(item);
			}
			System.out.println();
		}
		// 字符串浏览结束,依次弹出oprateStack数据，并压入tempList
		while (operateStack.size() != 0) {
			tempList.add(operateStack.pop());
		}
		System.out.print("后缀表达式：");
		for (String str : tempList) {
			System.out.print(str + " ");
		}
		return tempList;
	}
	
   /*计算表达式：从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，
    用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；
    重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果*/
	public static Float cal(List<String> list) {
		Stack<String> stack = new Stack<>();
		for (String item : list) {
			// if (item.matches("\\d+")){
			if (item.matches("\\d+(\\.\\d+)?")) {// 匹配整数或包括小数点的数字
				stack.push(item);
			} else {// 操作符
				float num1 = Float.parseFloat(stack.pop());
				float num2 = Float.parseFloat(stack.pop());
				Float res = 0f;
				switch (item) {
				case "+":
					res = num1 + num2;
					break;
				case "-":
					res = num2 - num1;
					break;
				case "*":
					res = num1 * num2;
					break;
				case "/":
					res = num2 / num1;
					break;
				default:
					break;
				}
				stack.push("" + res);// (""+res)有将int res转换成String的操作，保证栈内存储String型数据
			}
		}

		Float res = Float.parseFloat(stack.pop());
		return res;
	}
}
/*
class Operation {
	public static final int DEV = 2;
	public static final int MUL = 2;
	public static final int DEC = 1;
	public static final int ADD = 1;

	public static int getPrior(String rex) {
		int res = 0;
		switch (rex) {
		case "+":
			res = ADD;
			break;
		case "-":
			res = DEC;
			break;
		case "*":
			res = MUL;
			break;
		case "/":
			res = DEV;
			break;
		default:
			// System.out.println("未匹配字符");
			break;
		}
		return res;
	}
}*/